package middle.arrays;

import java.util.Stack;

/**
 * @Author Elephas
 * @Date 2022/2/13
 **/
@FunctionalInterface
public interface SetZeroes {
    void setZeroes(int[][] matrix);
}
class SetZeroesImpl1 implements SetZeroes{
    private int m;
    private int n;

    /**
     * space o(mn)
     * @param matrix
     */
    @Override
    public void setZeroes(int[][] matrix) {
        Stack<int[]> stack = new Stack<>();
        m = matrix.length;
        n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0){
                    stack.push(new int[]{i,j});
                }
            }
        }
        while(!stack.isEmpty()){
            int[] tuple = stack.pop();
            int x = tuple[0];
            int y = tuple[1];
            // clear the column
            for (int i = 0; i < m; i++) {
                matrix[i][y] = 0;
            }
            // clear the row
            for (int j = 0; j < n; j++) {
                matrix[x][j] = 0;
            }
        }
    }
}

class SetZeroesImpl2 implements SetZeroes{
    /**
     * spaces o(m + n)
     * @param matrix
     */
    private int m;
    private int n;
    private boolean[] rows;
    private boolean[] columns;
    @Override
    public void setZeroes(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        rows = new boolean[m];
        columns = new boolean[n];
        for (int i = 0; i < m; i++) {
            rows[i] = false;
        }
        for (int j = 0; j < n; j++) {
            columns[j] = false;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0){
                    rows[i] = true;
                    columns[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            if(rows[i]) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 0; j < n; j++) {
            if(columns[j]){
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

class SetZeroesImpl3 implements SetZeroes{
    static final int[][] TEST_01 = new int[][]{{1,1,1},{1,0,1},{1,1,1}};
    static final int[][] TEST_02 = new int[][]{{1},{0}};
    static final int[][] TEST_03 = new int[][]{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
    public static void main(String[] args) {
        new SetZeroesImpl4().setZeroes(TEST_03);
    }
    static final int CLEAR = 0;
    static final int RESERVE = 1;
    int m;
    int n;
    int rowIndex;
    int columnsIndex;
    int[][] matrix;
    /**
     * 若矩阵中没有 0 元素，则无需变更，
     * 若矩阵中存在 0 元素， 该元素所在行列均为0，可以利用它们作为辅助数组，分别有 o(m),o(n) 的空间
     * 利用该 o(m + n)空间作为辅助数组，复现一遍o(m + n)的实现，
     * 最后将该o(m + n) 的空间置0
     * spaces o(1)
     * @param matrix
     */
    @Override
    public void setZeroes(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        rowIndex = -1;
        columnsIndex = -1;
        this.matrix = matrix;
        boolean canBreak = findAuxArray();
        // 数组所有元素均不为0，直接返回
        if(!canBreak){
            return;
        }
        // 根据矩阵中的 0 来标记辅助数组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0){
                    updateAuxColumn(j);
                    updateAuxRow(i);
                }
            }
        }
        // 列清空
        for (int j = 0; j < n; j++) {
            if(canClearColumn(j)){
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 列辅助数组置为不清空状态
        for (int i = 0; i < m; i++) {
            matrix[i][columnsIndex] = RESERVE;
        }

        for (int i = 0; i < m; i++) {
            if(canClearRow(i)){
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 辅助数组置0
        for (int i = 0; i < m; i++) {
            matrix[i][columnsIndex] = 0;
        }
        for (int j = 0; j < n; j++) {
            matrix[rowIndex][j] = 0;
        }
    }
    private boolean canClearRow(int row){
        return matrix[row][columnsIndex] == CLEAR;
    }
    private boolean canClearColumn(int column){
        return matrix[rowIndex][column] == CLEAR;
    }
    private void updateAuxRow(int row){
        matrix[row][columnsIndex] = CLEAR;
    }
    private void updateAuxColumn(int column){
        matrix[rowIndex][column] = CLEAR;
    }
    private boolean findAuxArray(){
        boolean canBreak = false;
        for (int i = 0; i < m; i++) {
            if(canBreak){
                break;
            }
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0){
                    rowIndex = i;
                    columnsIndex = j;
                    canBreak = true;
                    break;
                }
            }
        }
        if(canBreak){
            for (int i = 0; i < m; i++) {
                if(matrix[i][columnsIndex] != 0){
                    matrix[i][columnsIndex] = RESERVE;
                }else{
                    matrix[i][columnsIndex] = CLEAR;
                }
            }
            for (int j = 0; j < n; j++) {
                if(matrix[rowIndex][j] != 0){
                    matrix[rowIndex][j] = RESERVE;
                }else {
                    matrix[rowIndex][j] = CLEAR;
                }
            }

        }
        return canBreak;
    }

}

class SetZeroesImpl4 implements SetZeroes{
    static final int CLEAR = 0;
    static final int RESERVE = 1;
    int m;
    int n;
    int rowIndex;
    int columnsIndex;
    int[][] matrix;

    @Override
    public void setZeroes(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        rowIndex = -1;
        columnsIndex = -1;
        this.matrix = matrix;
        boolean canBreak = findAuxArray();
        // 数组所有元素均不为0，直接返回
        if(!canBreak){
            return;
        }
        for (int i = 0; i < m; i++) {
            matrix[i][columnsIndex] = matrix[i][columnsIndex] == 0 ? CLEAR : RESERVE;
        }
        for (int j = 0; j < n; j++) {
            matrix[rowIndex][j] = matrix[rowIndex][j]== 0 ? CLEAR : RESERVE;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0){
                    matrix[rowIndex][j] = CLEAR;
                    matrix[i][columnsIndex] = CLEAR;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            if(matrix[i][columnsIndex] == CLEAR){
                for (int j = 0; j < n; j++) {
                    if(i != rowIndex) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }
        for (int j = n - 1; j >= 0; j--) {
            if(matrix[rowIndex][j] == CLEAR){
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            matrix[i][columnsIndex] = 0;
        }
        for (int j = 0; j < n; j++) {
            matrix[rowIndex][j] = 0;
        }
        return;
    }
    private boolean findAuxArray(){
        boolean canBreak = false;
        for (int i = 0; i < m; i++) {
            if(canBreak){
                break;
            }
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0){
                    rowIndex = i;
                    columnsIndex = j;
                    canBreak = true;
                    break;
                }
            }
        }
        return canBreak;
    }
}